package e_union_find.d_union_find_opt_by_rank;

/**
 * 优化： 将小组向大组合并改成将矮组向高组合并，将略微提高性能）
 *
 * 在数据量小的时候优势并不明显，甚至还要比上一个版本略慢
 * 这是因为小而高的组本来就十分罕见同时增加了判断条件
 *
 * 继续优化的思路：在find的同时做路径压缩处理!! 可将并查操作时间复杂度降至接近o(1)水平
 * 这是因为并查集并不限制一个根元素之下孩子元素的个数，最好的优化就是所有组的rank都不超过1
 */
public class UnionFind4 {
    private int[] pids; // 为了方便， 索引代表元素id，值代表该位置的元素所指向的pid
    private int[] rank; // rank[i]代表以i为根的组的高度
    private int count; // 并查集包含的元素个数

    /**
     * 传入 size
     * 构造一个以size为大小的并查集，组号从0递增到size-1
     *
     * @param size
     */
    public UnionFind4(int size) {
        this.count = size;
        this.pids = new int[size];
        this.rank = new int[size]; // 组成员人数不包括根，因此高度为0
        for (int i = 0; i < size; i++) {
            this.pids[i] = i;
        }
    }

    /**
     * 查找元素所在组的根id - O(1~n)
     *
     * @param p 待查找元素的id
     * @return 带查找元素所在组的根id
     */
    public int find(int p) {
        assert p >= 0 && p < this.count;
        // 向上找到组的根id
        while (p != pids[p]) {
            p = pids[p];
        }
        return p;
    }

    /**
     * 判断两个元素id之间是否处于相同的组  - O(1~n)
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 将p和q所在组联合成一个组   - O(1~n)
     * 将q所在的组的所有成员都拉入p所在的组中
     * 即让q所在组的根指向p所在组的根即可
     *
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        assert (p >= 0 && p < this.count) && (q >= 0 && q < this.count);

        int pRootID = find(p);
        int qRootID = find(q);

        if (pRootID == qRootID) return;
        if (rank[pRootID] < rank[qRootID]) { // q组高
            pids[pRootID] = qRootID; // 合并到q组
        } else if (rank[pRootID] > rank[qRootID]) { // p组高
            pids[qRootID] = pRootID; // 合并到p组
        }else { // 一样高则统一合并到q组
            pids[qRootID] = pRootID; // 合并到p组
            rank[pRootID] += 1; // 高度加1
        }
    }

    /**
     * 将所有元素都归入第一个元素的组中 - O(n)
     *
     * @param oids
     */
    public void unionAll(int... oids) {
        assert oids != null && oids.length > 1;
        int len = oids.length;
        for (int i = 1; i < len; i++) {
            union(oids[i-1],oids[i]);
        }
    }

    // TODO test method .. to be deleted
    public void testPrint() {
        System.out.print("id  -> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t" + i);
        }
        System.out.println();
        System.out.print("tid -> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t" + find(pids[i]));
        }
        System.out.println();
        System.out.print("rank-> ");
        for (int i = 0; i < count; i++) {
            System.out.print("\t" + rank[i]);
        }
        System.out.println("\n=======================");
    }

}
